package top.codetheory._05_二叉搜索树;

import java.util.Comparator;

/**
 * @author:
 * @since: 2023/11/28 14:05
 **/
public class RedBlackTree<E> extends BBST<E>  {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private Comparator<E> comparator;

    public RedBlackTree() {
        this(null);
    }

    public RedBlackTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    protected void afterRemove(Node<E> node, Node<E> replacement) {

        // 如果删除的节点是红色, 或者 用以取代node的子节点是红色  删除的节点是黑色节点, 度为1, 且他有一个红色的子节点, 这个红色节点就可以替代他
        if (isRed(node)) {
            black(node);
            return;
        }
        Node<E> parent = node.parent;
        // 删除的是根节点  也可以写为root == node
        if (parent == null) return;

        // 删除的是黑色叶子节点
        // 先区分黑兄弟是在父节点的左边还是右边
        boolean isLeft = parent.left == null || node.isLeftChildren();  // 这里有两种情况, 一种是如果是正在删除了的叶子节点的话, 那么会断开父亲指向他的线, 所以可以这样判断
                                                                            // 一种是他实际上没有删除, 所以不能用判空来判断
        Node<E> sibling = isLeft ? parent.right : parent.left;
        if (isLeft) {  // 被删除的节点在左边, 兄弟节点在右边
            if (isRed(sibling)) {
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.right;
            }

            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) afterRemove(parent, null);
            } else {
                if (isBlack(sibling.right)) {
                    rotateLeft(sibling);
                    sibling = parent.right;
                }
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateRight(parent);
            }
        } else {// 被删除的节点在右边, 兄弟节点在左边, PPT上就是这种
            if (isRed(sibling)) {  // 兄弟节点是红色
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;  // 更换兄弟节点
            }

            // 兄弟节点是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                boolean parentBlack = isBlack(parent);  // 先看看他的父节点是否是黑色, 如果是黑色就会产生下溢
                black(parent);
                red(sibling);
                if (parentBlack) afterRemove(parent, null);  // 处理下溢
            } else {  // 兄弟节点有红色的情况, 可以向兄弟节点借
                // 这里有三种情况, 都要进行旋转, 分别是lr r r, 我们先判断lr的情况, 把他的l先做了
                if (isBlack(sibling.left)) {  // 兄弟的左边是黑色
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                // 统一r
                color(sibling, colorOf(parent));  // 兄弟节点继承父节点的颜色
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }

    }

    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;

        // 添加的是根节点
        if (parent == null) {
            black(root);  // 染色
            return;
        }

        // 如果父节点是黑色的, 不用做任何处理    -- 4种情况
        if (isBlack(parent)) return;

        // uncle 节点                          -- 上溢的4种情况
        Node<E> uncle = node.uncle();
        Node<E> grand = red(parent.parent);
        if (isRed(uncle)) {
            black(parent);
            black(uncle);
            // 祖父节点当做新添加的节点
            afterAdd(grand);
            return;
        }

        // 叔父节点不是红色                     -- LL/RR/LR/RL
        if (parent.isLeftChildren()) {  // L
            if (node.isLeftChildren()) {  // LL
                black(parent);
            } else {  // LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        } else {  // R
            if (node.isLeftChildren()) {  // RL
                black(node);
                rotateRight(parent);
            } else {  // RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     * 上色
     * @param node 需要上色的节点
     * @param color 染为什么颜色
     * @return 染色后的节点
     */
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return node;
        ((RedBlackNode<E>)node).color = color;
        return node;
    }

    /**
     * 染成红色
     * @param node 需要染色的节点
     * @return 染色的节点
     */
    private Node<E> red(Node<E> node) {
        return color(node, RED);
    }

    /**
     * 染成黑色
     * @param node 需要染色的节点
     * @return 染色的节点
     */
    private Node<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    /**
     * 查看节点是什么颜色的
     * @param node 需要查看的节点
     * @return 颜色
     */
    private boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RedBlackNode<E>)node).color;
    }

    /**
     * 判断节点是否为黑色
     * @param node 需要判断的节点
     * @return 是否为黑色
     */
    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    /**
     * 判断节点是否为红色
     * @param node 需要判断的节点
     * @return 是否为红色
     */
    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RedBlackNode<>(element, parent);
    }

    /**
     * 红黑树的节点
     * @param <E> 泛型
     */
    private static class RedBlackNode<E> extends Node<E> {
        boolean color = RED;

        public RedBlackNode(E element, Node<E> parent) {
            super(element, parent);
        }
    }

    @Override
    public Object string(Object node) {
        RedBlackNode<E> myNode = (RedBlackNode<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        String color = myNode.color == RED ? "red" : "black";
        return myNode.element + "_p(" + parentString + ")" + "_c(" + color + ")";
    }

//    @Override
//    protected void afterRemove(Node<E> node, Node<E> replacement) {
//
//        if (isRed(node)) return; // 如果删除的节点是红色, 那么不用做任何处理
//
//        // 用以取代node的子节点是红色  删除的节点是黑色节点, 度为1, 且他有一个红色的子节点, 这个红色节点就可以替代他
//        if (isRed(replacement)) {
//            black(replacement);
//            return;
//        }
//        Node<E> parent = node.parent;
//        // 删除的是根节点  也可以写为root == node
//        if (parent == null) return;
//
//        // 删除的是黑色叶子节点
//        // 先区分黑兄弟是在父节点的左边还是右边
//        boolean isLeft = parent.left == null || node.isLeftChildren();  // 这里有两种情况, 一种是如果是正在删除了的叶子节点的话, 那么会断开父亲指向他的线, 所以可以这样判断
//        // 一种是他实际上没有删除, 所以不能用判空来判断
//        Node<E> sibling = isLeft ? parent.right : parent.left;
//        if (isLeft) {  // 被删除的节点在左边, 兄弟节点在右边
//            if (isRed(sibling)) {
//                black(sibling);
//                red(parent);
//                rotateRight(parent);
//                sibling = parent.right;
//            }
//
//            if (isBlack(sibling.left) && isBlack(sibling.right)) {
//                boolean parentBlack = isBlack(parent);
//                black(parent);
//                red(sibling);
//                if (parentBlack) afterRemove(parent, null);
//            } else {
//                if (isBlack(sibling.right)) {
//                    rotateLeft(sibling);
//                    sibling = parent.right;
//                }
//                color(sibling, colorOf(parent));
//                black(sibling.right);
//                black(parent);
//                rotateRight(parent);
//            }
//        } else {// 被删除的节点在右边, 兄弟节点在左边, PPT上就是这种
//            if (isRed(sibling)) {  // 兄弟节点是红色
//                black(sibling);
//                red(parent);
//                rotateRight(parent);
//                sibling = parent.left;  // 更换兄弟节点
//            }
//
//            // 兄弟节点是黑色
//            if (isBlack(sibling.left) && isBlack(sibling.right)) {
//                boolean parentBlack = isBlack(parent);  // 先看看他的父节点是否是黑色, 如果是黑色就会产生下溢
//                black(parent);
//                red(sibling);
//                if (parentBlack) afterRemove(parent, null);  // 处理下溢
//            } else {  // 兄弟节点有红色的情况, 可以向兄弟节点借
//                // 这里有三种情况, 都要进行旋转, 分别是lr r r, 我们先判断lr的情况, 把他的l先做了
//                if (isBlack(sibling.left)) {  // 兄弟的左边是黑色
//                    rotateLeft(sibling);
//                    sibling = parent.left;
//                }
//                // 统一r
//                color(sibling, colorOf(parent));  // 兄弟节点继承父节点的颜色
//                black(sibling.left);
//                black(parent);
//                rotateRight(parent);
//            }
//        }
//
//    }
}